package com.interview.javabase.algorithm;

import java.util.Arrays;
import java.util.List;

/**
 * @author www.byteblogs.com
 * @date 2021-08-23
 * @since 2.0
 */
public class 凑零钱 {

    public static void main(String[] args) {
        int i = coinChange(Arrays.asList(1, 2, 5), 11);
        System.out.println(i);
    }

    public static int coinChange(List<Integer> coins, int amount) {
        int[] db = new int[amount + 1];

        Arrays.fill(db, amount + 1);

        db[0] = 0;

        for (int i = 0; i < db.length; i++) {
            for (Integer coin : coins) {
                if (i < coin) {
                    continue;
                }

                db[i] = Math.min(db[i], 1 + db[i - coin]);
            }
        }

        return db[amount] == amount + 1 ? -1 : db[amount];


    }
}
